package Hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

//三数之和
public class sum3 {
    /*给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
    满足 i != j、i != k 且 j != k ，
    同时还满足 nums[i] + nums[j] + nums[k] == 0 。
    请你返回所有和为 0 且不重复的三元组。
    注意：答案中不可以包含重复的三元组。
        示例 1：
        输入：nums = [-1,0,1,2,-1,-4]
        输出：[[-1,-1,2],[-1,0,1]]
        解释：
        nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
        nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
        nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
        不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
        注意，输出的顺序和三元组的顺序并不重要。*/

    /**
     *思路过程：
     * 题目解析：给一个整数数组，要求根据数组里面的不同索引的值得到一个三元组，使得相加为0
     *          要求：1. i、j、k不能相等
     *               2. 不重复
     *               3. 返回三元组 不是返回次数了
     * 思路：
     * 1.哈希法：先遍历数组nums，得到一个和map集合，key为sum，value为索引，该数组是由nums数组中两两相加组成，然后再去相加另外一个？
     * 不对，不能重复：用map存？
     * 2.双指针法：感觉有去重的时候，用双指针法比较好用
     * 如果要进行双指针法的排序相关，要对nums先进行从小到大排序，方便进行移动指针
     * 思想：定义i先固定在0，然后left和right在左右，然后将这三个对应的值相加，如果>0，则证明太大了，right-1，如果<0 则证明太小了，left+1
     * 去重逻辑：因为这里的三元组不仅仅i、j、k不能重复，他的对应的值也不能重复，所以这里注意
     * [-1,0,1,2,-1,-4]
     * 排完序后：[-4,-1,-1,0,1,2]
     * 要去重其实很简单，比如刚开始：i是-1(索引为1)，left是-1(索引为2），right是2，那么因为<0 所以是left移动，直到移动到0，此时[-1,0,1]是一个三元组
     * 然后i++
     * 这里的i又是-1（素引为3)，那么因为这个值和num[i-1]是相同的【因为已经是排完序了，所以相同的值一定是在一起的】,然后left和right都是在后面
     * 就意味着因为i又是-1，那么后面left和right在移动的过程中，如果有sum=0的，最后得到的值一定也是和前一个是三元组相同，即又是[-1,0,1] 而我们的三元组要不同的
     * 所以这里去重的逻辑是：if (num[i]==num[i-1]) i++; continue; 直接开启下一个循环
     * left和right的去重逻辑和这个一样
     * 注意这里不是num[i]==num[i+1] 去比较 因为如果是这样的话，就不是去重的逻辑了 而是不允许三元组出现重复的元素了 但这里是允许的，只是要求三元组不能重复
     *如:[0,0,0] 这里是一个正确的结果集，但如果是if (num[i]==num[i+1]) i++; continue; 那么就会导致失去这个正确的结果
     * todo:本质上是因为if (num[i]==num[i-1]) i++; continue; 这个能去跳过循环是因为 排序后的 比如[0,-1,-1,1] 如果i的索引是1时，那么此时就得到了正确的结果[0,-1,1]
     *      即前面一个是根据i=-1时，已经得到了一个正确的结果集了，这里是对第一个元素a去重【如果让if (num[i]==num[i+1]) i++; continue; 去进行去重 那么就会让比如：i为索引1时，因为跟索引2相同，所以跳过，失去了正确解，所以应该是跟之前的num[i-1]去比较】
     *      并且这里并不会导致a=-1时的结果只剩下一个：[-1,0,1]
     *      因为后面的left和right是while，他会将当第一个元素为-1的所有符合的结果都存起来 即：[-1,0,1] 和 [-1,-1,2]都存起来 所以就不需要第二个的-1了
     */
    //得到结果的逻辑的注意事项：
    // 排序后+要得到对应的值，不只是要结果(因为双指针可以得到对应的索引==》得到对应的结果）+不重复=双指针【因为left和right的一般结束条件是：left<right 所以不重复很重要

    public static List<List<Integer>> threeSum(int[] nums) {
        //先排序咯,从小到大排序
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();
        int i=0;
        int left=1;
        int right=nums.length-1;
        // 要找到[a,b,c] 这个三元组 现在 a是i、b是left、c是right
        while (i<nums.length){

            if(nums[i]>0){
                return res;
            }
            // 对a去重
            if(i>0&&nums[i]==nums[i-1]){
                i++;
                left=i+1;
                continue;
            }
            while (left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }else {
                    // 如果=0
                    res.add((Arrays.asList(nums[i], nums[left], nums[right])));
                    // 注意这里不能让他有的话就结束循环，要是有两个呢？所以还得继续变化移动
                    // 对b和c去重:这里的去重是和下一位做比较 让left和right不断往中间移动即可，而不是和他的前一位：因为上面已经和num[left] 得到一次结果了 所以如果之后的left+1还是num[left]的话，不用比较 因为得到的结果是一样的 所以跳过
                    //todo:和a去重的区别是：a是还没发生，所以不能去重 得发生后才能去重，所以是和上一个比较 这里是已经发送【即已经对nums[left]进行处理了，所以是和下一个比较 一样即可跳过
                    // todo:注意这里是while 而不是if 如果是while的话 就可以连续去重了 if的话去重不干净,因为只去重一次
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
            i++;
            left=i+1;
            right=nums.length-1;
        }
        return res;
    }

    public static void main(String[] args) {
        threeSum(new int[]{-1,0,1,2,-1,-4});
    }
}
